import java.util.*;


public class Solution {

    static class Node {
        int key;
        int val;
        Node prev;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    public static Map<Integer, Node> mp = new HashMap<>();
    public static Node head = new Node(-1, -1);
    public static Node tail = new Node(-1, -1);
    public static int size = 0;

    public Solution(int capacity) {
        // write code here
        size = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public void set(int key, int value) {
        // write code here
        if(!mp.containsKey(key)){
            Node node = new Node(key,value);
            mp.put(key,node);
            if(size <= 0){
                remove();
            }else size--;
            add(node);
        }else{
            mp.get(key).val = value;
            move(mp.get(key));
        }
    }

    public int get(int key) {
        // write code here
        if(mp.containsKey(key)){
            move(mp.get(key));
            return mp.get(key).val;
        }else return -1;
    }

    public static void move(Node node){
        if(node.prev == head)return;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        add(node);
    }

    public static void add(Node node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    public static void remove(){
        mp.remove(tail.prev.key);
        tail.prev.prev.next = tail;
        tail.prev = tail.prev.prev;
    }










    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail(ListNode head) {
        // write code here
        List<Integer> l = new ArrayList<>();
        while (head != null) {
            l.add(head.val);
            head = head.next;
        }
        int left = 0, right = l.size() - 1;
        while (left < right) {
            //System.out.println(l.get(left) + " " + l.get(right));
            if (l.get(left) != l.get(right)) return false;
            // int x = l.get(left);
            // int y = l.get(right);
            // if(x != y)
            //     return false;
            left++;
            right--;
        }
        return true;
    }
    public int[][] rotateMatrix(int[][] mat, int n) {
        // 先上下翻转
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[n - i - 1][j];
                mat[n - i - 1][j] = temp;
            }
        }
        // 再进行矩阵转置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        return mat;
    }

}